(1) Field of the Invention
The present invention relates to encryption technology as information security technology and especially to secret communication, digital signature and key-sharing technology using an elliptic curve.
(2) Description of the Prior Art
1. Public-key Encryption
Recently, data communication based on computer technology and communication technology has become widely available, and in this data communication, a secret communication mode or a digital signature mode is used. Here, the secret communication mode is a mode to communicate without leaking communication contents to a person other than the other specified party of the communication. Moreover, the digital signature mode is a mode that shows the correctness of communication contents to the other party of the communication and certifies the identity of the originator.
In the secret communication mode or digital signature mode, an encryption mode called a public-key encryption is used. The public-key encryption is a mode to easily manage encryption keys that are different for each of the other parties of the communication when there are a plurality of other parties of the communication, and is an indispensable fundamental technology to communicate with the plurality of other parties of the communication. In the secret communication using the public-key encryption, an encryption key and a decryption key are different, wherein the decryption key is secret and the encryption key is public.
As a base of security of this public-key encryption, a discrete logarithm problem is used. As for the discrete logarithm problem, there are what is defined on a finite field and what is defined on an elliptic curve as representatives. Moreover, the discrete logarithm problem is described in detail in “A Course in Number theory and Cryptography” by Neal Koblitz, Springer-Verlag, 1987.
2. The Discrete Logarithm Problem on an Elliptic Curve
The discrete logarithm problem on an elliptic curve is described below. The discrete logarithm problem on the elliptic curve is the elliptic curve that defines E (GF (p)) on a finite field GF (p), in the case that the elliptic curve E is divisible by a large prime number, element G included in the elliptic curve is a base point. In this case, it is a question that in the case that an integer x that satisfies (Equation 1) Y=x*G to a given element Y included in the elliptic curve exists, seek x.
Here, p is a prime number and GF (p) is a finite filed that has p pieces of element. Additionally, within this patent specification, the symbol * shows calculation to add element included in the elliptic curve plural times, x*G, as the below-mentioned equation shows, means that element G is added x times.x*G=G+G+G+ . . . +G 
The reason that makes the discrete logarithm problem a premise of the security of the public-key encryption is that the above-mentioned problem to the finite field that has many elements is extremely difficult.
3. ElGamal Signature that Applies the Discrete Logarithm Problem on the Elliptic Curve
Thereinafter, the digital signature mode by ElGamal signature that applies discrete logarithm problem on the elliptic curve is explained by using FIG. 1. This figure is a sequence diagram that shows procedures of the digital signature mode by the above-mentioned ElGamal signature. A user A 11, a management center 12 and a user B13 are connected by network. Assume that p is a prime number and an elliptic curve defined on a finite field GF(p) is E. Assume a base point of E is G and the order of E is q. In other words, q is the smallest positive integer to satisfies (Equation 2) q*G=0
Moreover, the point (∞,∞), where both of x and y coordinates are ∞, is called an infinite point, and is represented by 0. This 0, when the elliptic curve is considered as a group, carries out a function of “zero element”.
(1) Generation of the Public Keys by the Management Center 12
The management center 12 generates the public key YA of the user A 11, using the secret key xA of the user A 11 that is notified in advance, and complying with the equation 3 (Step S141˜S142).YA=xA*G   (Equation 3)
Thereafter, the management center 12 releases the prime number p, the elliptic curve E and the base point G to the public as system parameters, and releases the public key YA of the user A 11 to another user B 13 (Step S143˜S144).
(2) Generation of a Signature by the User A11
The user A 11 generates a random number k (Step S145). Then, the user A 11 calculates (Equation 4) R1=(rx, ry)=k*G (Step S 146) and calculates s from (Equation 5) s×k=m+rx×xA (mod q). Here, m is a message that the user A 11 transmits to the user B 13. Furthermore, the user A 11 transmits obtained (R1, s) as a signature with the message m to the user B 13 (Step S148).
(3) The Verification of the Signature by the User B 13
The user B 13 confirm the identity of the user A 11 by judging whether (Equation 6) s*R1=m*G+rx*YA satisfies or not (Step S149). This is obvious because
                                                                        s                *                                  R                  1                                            =                            ⁢                                                {                                                            (                                                                        (                                                      m                            +                                                          rx                              ×                              xA                                                                                )                                                /                        k                                            )                                        ×                    k                                    }                                *                G                                                                                        =                            ⁢                                                (                                      m                    +                                          rx                      ×                      xA                                                        )                                *                G                                                                                        =                            ⁢                                                m                  *                  G                                +                                                      (                                          rx                      ×                      xA                                        )                                    *                  G                                                                                                        =                            ⁢                                                m                  *                  G                                +                                  rx                  *                  YA                                                                                        (                  Equation          ⁢                                          ⁢          7                )            satisfies.4. Addition of Points on the Elliptic Curve and Calculation Quantity by Double Multiplication
In each of the generation of the public key, the generation of the signature and the verification of the signature in the digital signature mode that is indicated above by ElGamal signature that applies the discrete logarithm problem on the elliptic curve, the calculation of scalar multiplication of points on the elliptic curve is carried out. For example, “xA*G” indicated in the equation 3, “k*G” indicated in the equation 4, “s*R1”, “m*G” and “rx*YA” indicated in the equation 6 are the calculation of the scalar multiplication of the points on the elliptic curve.
The calculation formula of the elliptic curve is explained in detail in “Efficient elliptic curve exponentiation” (written by Miyaji, Ono, and Cohen, Advances in cryptology-proceedings of ICICS, 97, Lecture notes in computer science, 1997, Springer-Verlag, 282–290).
Thereinafter, the calculation formula of the elliptic curve is explained. Assume that the equation of the elliptic curve is y2=x3+a×x+b, the coordinates of a given point P are (x1, y1) and the coordinates of a given point Q are (x2, y2). Here, assume that the coordinates of the point R fixed by R=P+Q are (x3, y3).
In the case of P≠Q, R=P+Q becomes the calculation of addition. The formulae of addition are as follows:x3={(y2−y1)/(x2−x1)}2x1−x2 y3={(y2−y1)/(x2−x1)}(x1−x3)−y1 
In the case of P=Q, R=P+Q=P+P=2×P satisfies, R=P+Q becomes double multiplication.
The formulae of double multiplication are as follows:x3={(3x12+a)/2y1}2−2x1 y3={(3x12+a)/2y1)(x1−x3)−y1 
Moreover, the above-mentioned calculation is a calculation on the finite field in which elliptic curve is defined. As was indicated above, in 2-term coordinates or affine coordinates, namely, the coordinates described until now, in case that addition calculation is carried out, every one addition on the elliptic curve needs one inverse number calculation. In general, an inverse number calculation needs about 10 times calculation quantity compared with a multiplication on a finite filed.
Then, to reduce the calculation quantity, 3-term coordinates called projection coordinates are used. Projection coordinates are coordinates comprising three terms X, Y, Z, in relation to the coordinate (X, Y, Z) and the coordinate (X′, Y′, Z′), a given number n exists and there is a relationship X′=n X, Y′=n Y, Z′=n Z satisfies, (X, Y, Z)=(X′, Y′, Z′) satisfies. An affine coordinate (x, y) and a projection coordinate (X, Y, Z) corresponds to each other in the below-mentioned relationship.(x, y)→(x, y, 1)(X, Y, Z)→(X/Y, Y/Z)(in the case of Z≠0)
Here, the symbol → is used as the below-mentioned meaning. When a given element in a set S1 corresponds to one element in a set S2, the relationship is indicated by S1→S2.
Thereinafter, all the calculations of the elliptic curve are in the projection coordinates. Next, the addition formulae and the double multiplication formulae on the projection coordinates are explained. These formulae have, of course, consistency with the addition formulae and the double multiplication formulae in the affine coordinates. The calculation of scalar multiplication is realized by the repeated calculation of the addition and the double multiplication on the elliptic curve. Out of these calculations of scalar multiplication, the calculation quantity of addition does not depend on the parameters of the elliptic curve, but the calculation quantity of the double multiplication depends on the parameters of the elliptic curve.
Here, assume that p is a prime number of 160 bits and the elliptic curve is E: y2=x3+ax+b, and when the elements P, Q on the elliptic curve are indicated by P=(X1, Y1, Z1) and Q=(X2, Y2, Z2), R=(X3, Y3, Z3)=P+Q is obtained as follows:
(i) in the case of P≠Q
In this case, it is a calculation of an addition.
(Step 1-1) The Calculation of an Intermediate Value
The below-mentioned equations are calculated.U1=X1×Z22  (Equation 8)U2=X2×Z12  (Equation 9)S1=Y1×Z23  (Equation 10)S2=Y2×Z13  (Equation 11)H=U2−U1  (Equation 12)r=S2−S1  (Equation 13)(Step 1-2) The Calculation of R=(X3, Y3, Z3)
The below-mentioned equations are calculated.X3=−H3−2×U1×H2+r2  (Equation 14)Y3=−S1×H3+r×(U1×H2−X3)  (Equation 15)Z3=Z1×Z2×H  (Equation 16)(ii) in the case of P=Q (namely, R=2P)
In this case, it is a calculation of double multiplication.
(Step 2-1) The Calculation of an Intermediate Value
The below-mentioned equations are calculated.S=4×X1×Y12  (Equation 17)M=3×X12+a×Z14  (Equation 18)T=−2×S+M2  (Equation 19)(Step 2-2) The Calculation of R=(X3, Y3, Z3)
The below-mentioned equations are calculated.X3=T  (Equation 20)Y3=−8×Y14+M×(S−T)  (Equation 21)Z3=2×Y1×Z1  (Equation 22)
Next, the calculation quantity in the case of the addition and the double multiplication of the elliptic curve are explained. Here, the calculation quantity by one multiplication is indicated by 1 Mu1, and the calculation quantity by one square multiplication is indicated by 1 Sq. Moreover, in an ordinary microprocessor, 1 Sq≈0.8 Mu1 satisfies.
According to the above-mentioned examples, the calculation quantity of the addition on the elliptic curve indicated in the case of P≠Q is obtained by counting the numbers of the multiplication and the square multiplication in the equations 8˜16 and is 12 Mul+4 Sq. This is obvious because the calculation quantities of the addition in the equations 8, 9, 10, 11, 14, 15 and 16 are 1 Mul+1 Sq, 1 Mul+1 Sq, 2 Mul, 2 Mul, 2 Mul+2 Sq, 2 Mul and 2 Mul, respectively.
Additionally, according to the above-mentioned examples, the calculation quantity of the double multiplication on the elliptic curve indicated in the case of P=Q is obtained by counting the numbers of the multiplication and the square multiplication in the equations 17˜22 and 4 Mul+6 Sq. This is obvious because the calculation quantities of the square multiplication in the equations 17, 18, 19, 21 and 22 are 1 Mul+1 Sq, 1 Mul+3 Sq, 1 Sq, 1 Mul+1 Sq and 1 Mul, respectively.
Moreover, in the above-mentioned counting of the number, for example, since the equation 14 H3 can be unfolded to H3=H2×H, the calculation quantity of H3 is assumed to be 1 Mul+1 Sq, and since the equation 18 Z14 can be unfolded to Z14=(Z12)2, the calculation quantity of Z14 is assumed to be 2 Sq.
Moreover, as for the equation 14 H2, in the above-mentioned process of calculating H3, H2 is calculated, therefore the calculation quantity of H2 is not counted again. Additionally, at the time of counting the number of multiplication, the number of multiplication that is carried out by multiplying a certain value by a small value is not counted. Thereinafter, the reason is explained. The small values mentioned here are, in the equations 8˜22, the small fixed values that are objects for multiplication and, to be more specific, are the values such as 2, 3, 4, 8 and so forth. These values can be indicated by the binary of 4 bits at most. On the other hand, the other variable numbers have the value of 160 bits ordinarily.
Generally, in a microprocessor, the multiplication of the multiplier and the multiplicand is carried out by the repetition of the shift of the multiplicand and the addition. In other words, for each bit of the multiplier represented by binary, in the case that this bit is 1, in order that the least significant bit of the multiplicand represented by binary matches the position where this bit exists, by shifting the multiplicand, one bit string is obtained. In relation to all the bits of the multiplier, all of at least one bit of string obtained by this means are added.
For example, in the multiplication of the multiplier of 160 bits and the multiplicand of 160 bits, the multiplicand of 160 bits is shifted for 160 times, 160 bit strings are obtained and the obtained 160 bit strings are added. On the hand, in the multiplication of the multiplier of 4 bit and the multiplicand of 160 bits, the multiplicand of 160 bits is shifted for 4 times, 4 bit strings are obtained and the obtained 4 bit stirrings are added.
Since the multiplication is carried out as was indicated above, in the case that the multiplication is carried out by multiplying a certain value by a small value, the number of the above-mentioned repetition becomes small. Accordingly, the calculation quantity can be regarded as small and therefore it is not counted as the number of the multiplication. As was explained above, in the case of carrying out the double multiplication of the elliptic curve, the equation 18 includes the parameter a of the elliptic curve. As the value of this parameter a, for example, when a small value is adopted, the calculation quantity of the double multiplication on the elliptic curve can be reduced by 1 Mul and becomes 3 Mul+6 Sq. Moreover, as for the addition, even though the parameter of the elliptic curve is changed, the calculation quantity does not change.
5. Selection of an Elliptic Curve Suitable for Encryption
Next, the method for selecting an elliptic curve suitable for encryption is explained. Moreover, as for the detail, it is written in “IEEE P1363 Working draft” (issued by IEEE on Feb. 6, 1997). The elliptic curve suitable for encryption is obtained by repeating the steps below.
(Step 1) An Arbitrary Selection of an Elliptic Curve
Arbitrary parameters a and b on the infinite field GF (p) are selected. Here, a and b satisfy the equation 23 and p is a prime number.4×a3+27×b2≠0(mod p)  (Equation 23)
Assume that the elliptic curve is E: y2=x3+a×x+b by using the selected a and b.
(Step 2)
To judge whether it is the elliptic curve suitable for encryption, the number of the elements of the elliptic curve E, #E(GF (p)) is calculated, in the case that #E (GF (p)) is divisible by a large prime number (condition 1), and that #E (GF (p))−(p+1)≠0, −1 (condition 2), the elliptic curve E is adopted.
As was explained above, in the case that as the parameter a of the elliptic curve, a fixed small value is elected, although the calculation quantity in the calculation of the scalar multiplication of the elliptic curve is reduced, there is a problem that it is difficult to select a safe elliptic curve suitable for encryption by fixing the parameter in advance.
Conversely, by using the selection method explained above, in the case of selecting a safe elliptic curve suitable for encryption, it is not always possible to select a small value as the parameter a of the elliptic curve, and therefore there is a problem that the calculation quantity cannot be reduced. Thus, to select a safe elliptic curve suitable for encryption and to reduce the calculation quantity in the elliptic curve, there are problems that are contradictory and antagonistic to each other.
6. A Conventional Elliptic Curve Converting Device
To solve the above-mentioned problem, in the Japanese Patent No. 3050313 “AN ELLIPTIC CURVE CONVERTING DEVICE, AND DEVICE AND SYSTEM FOR UTILIZATION”, the below-mentioned elliptic curve converting device is indicated. This conventional elliptic curve converting device is a device that converts the inputted and arbitrary elliptic curve E: y2=x3+ax+b without changing its order into the elliptic curve E: y2=x3+ax+b with a small coefficient a (a=−3 and so forth). In other words, maintaining safety, the elliptic curve that is capable of reducing further the calculation quantity is generated.
This device converts the inputted elliptic curve into an isomorphic elliptic curve.
The elliptic curve converting device comprises, as FIG. 2 shows, a parameter receiving unit 110, a converting coefficient acquiring unit 120, a converted elliptic curve calculating unit 130, a parameter sending unit 140.
The parameter receiving unit 110 receives, from outside devices, parameters a and b, an element G on the elliptic curve and a prime number p. Here, p is a prime number of 160 bits.
The outside devices include an encryption device using public-key encryption, a decryption device, a digital signature device, a digital signature verification device, a key-sharing device and so forth. The outside devices use the discrete logarithm problem on the elliptic curve as the premise for the security of the public-key encryption and have the elliptic curve. Here, the elliptic curve that is constructed on the infinite field GF (p) arbitrarily is indicated by E: y2=x3+ax+b, and the element G is an arbitrary point on the elliptic curve and is indicated by G=(x0, y0).
the converting coefficient acquiring unit 120 has a function T (i). The function T (i) has, in the case of i=0, 1, 2, 3 4, the values −3, 1, −1, 2, −2, respectively. Additionally, the function T (i) has, in the case of i=5, 6, 7, 8, 9, 10, 11, . . . , the values 3, 4, −4, 5, −5, 6, −6 . . . , respectively.
The converting coefficient acquiring unit 120 calculates a converting coefficient t that begins from i=0, increases the value of i one by one, satisfies−231+1≦T(i)≦231−1,  (Equation 24)andT(i)=t4×a(mod p),  (Equation 25)and is an element on the infinite field GF (p).
Here, the equation 24 indicates that T (i) is taken on to be less than 32 bits. Moreover, the function T (i) has, in the case of i=0, the value −3 and the converting coefficient acquiring unit 120 refers to the value of the function T (i), beginning from i=0 and adding the value of i one by one, and therefore the value −3 is referred to at the beginning.
Additionally, the function T (i) has, except that it has the value −3 in the case of i=0, the values in sequence from a small absolute value to a large absolute value, and therefore the function T (i) can be referred to in sequence from a small absolute value.
The converted elliptic calculating unit 130 calculates, respectively and as follows, parameters a′ and b′ of the converted elliptic curve Et: y′2=x′3+a′×x′+b′ that is constructed on the infinite field GF (p).a′=a×t4  (Equation 26)b′=b×t6  (Equation 27)
Additionally, the converted elliptic curve calculating unit 130 calculates the element Gt=(xt 0, yt 0) on the converted elliptic curve Et corresponding to the element G as follows:xt0=t2×x0  (Equation 28)yt0=t3×y0  (Equation 29)
Moreover, an arbitrary point on the elliptic curve E is converted into one point on the converted elliptic curve Et defined by the parameters a′ and b′ generated as was stated above.
The parameter sending unit 140 sends out the calculated parameters a′ and b′ on the converted elliptic curve Et, and an element Gt (xt 0, yt 0) to the outside devices.
The conventional elliptic curve converting device like this operates as follows:
The parameter receiving unit 110 receives the prime number p, the parameters a and b (Step S151), and the element G on the elliptic curve (Step S152) from the outside devices. Next, the converting coefficient acquiring unit 120 calculates a converting coefficient (Step S153), the converted elliptic curve calculating unit 130 calculates the parameters a′ and b′ on the converted elliptic curve Et constructed on the infinite field GF (p) and the element Gt=(xt 0, yt 0) on the converted elliptic curve corresponding to the element G (Step S154), and the parameters sending unit 140 sends out the calculated parameters a′ and b′, and the element Gt (xt 0, yt 0) (Step S155).
Moreover, the detailed operations of the converting coefficient acquiring unit 120 are as follows:
The converting coefficient acquiring unit 120 sets a value 0 to i (Step S161). Next, the converting coefficient acquiring unit 120 judges that as for the function T (i), whether
−231+1≦T (i)≦231−1 satisfies or not. When the equation does not satisfy (Step S162), the converting coefficient acquiring unit 120 finishes the operations. When the equation satisfies (Step S162), the converting coefficient acquiring unit 120 calculates a coefficient t that turns out to beT(i)=t4×a(mod p)(Step S163), judges whether the calculated coefficient t is an element on the infinite field GF (p) or not, when it is the element on the infinite field GF (p) (Step S164), the converting coefficient acquiring unit 120 finishes the operations. When it is not an element on the infinite field GF (p) (Step S164), the converting coefficient acquiring unit 120 adds 1 to i (Step S165) and backs the control to Step S162 again.
Next, the converted elliptic curve calculating unit 130 operates as follows:
The converted elliptic curve calculating unit 130 calculates a parameter a′=a×t4 of the converted elliptic curve constructed on the infinite field GF (p) (Step S 171), and a parameter b′=b×t6 (Step S172). Additionally, the converted elliptic curve calculating unit 130 calculates, as the element Gt=(xt0, yt0) corresponding to the element G, xt0=t2×x0(Step S173) and yt0=t3×y0(Step 174).
This conventional elliptic curve converting device converts the inputted elliptic curve into an isomorphism of the elliptic curve. At Step 164, when T (i)=−3, only in the case that t of the equation 23 is an element of GF (p), it is possible to convert into the elliptic curve that has an equation y2=x3−3x+b.
Here, to be −3=a×t4, the forth root of −3/a on GF (p) must exist. As for an arbitrary x, since the probability that the square root of x on GF (p) exists is 1/2, the probability that the fourth root exists is “the probability that a square root of the square root exists”, and therefore 1/2×1/2=1/4. Accordingly, the probability that the above-mentioned t is an element of GF (p) is low at 1/4, and therefore it is not always possible to convert into the elliptic curve that has the equation y2=x3−3x+b.
7. Montgomery-type Elliptic Curve
The above-mentioned elliptic curve converting device makes only the elliptic curves whose equation is y2=x3+a×x+b as its objects. The elliptic curve like this is called a Weierstrass-type elliptic curve.
On the other hand, the elliptic curve whose equation is B×y2=x3+A×x2+x is called a Montgomery-type elliptic curve. This elliptic curve is known that the addition and the double multiplication of points are fast, and the calculation quantities are 4 Mul+2 Sq and 3 Mul+2 Sq, respectively. As was stated in above-mentioned 5, the calculation quantities of the addition and the double multiplication of the Weierstrass-type elliptic curve are 12 Mul+4 Sq and 4 Mul+6 Sq, respectively. Consequently, the Montgomery-type elliptic curve is faster in the addition and the double multiplication of the points. The Montgomery-type elliptic curve is described in detail in “Speeding the Pollard and Elliptic Curve Methods of Factorization” (written by P. L. Montgomery, Math. of Comp. 48, 1987, pp. 243–264).
On the other hand, in a method to generate a safe elliptic curve, there is a case of generating a safe elliptic curve by doing the order calculation and judging whether the elliptic curve is safe or not. Here, in the order calculation, the elliptic curve that is used is also the Weierstrass-type. Consequently, the elliptic curve generated by this method is limited to the Weierstrass-type.
By a similar way of thinking of the conventional elliptic curve converting device, it is thinkable to convert a Weierstrass-type elliptic curve into a Montgomery-type elliptic curve by using the isomorphism of the elliptic curve. Here, as in the case of seeking the elliptic curve that satisfies a=−3 in the conventional elliptic curve converting device, the conversion is not always possible. In other words, the Weierstrass-type elliptic curves which cannot be converted into the Montgomery-type elliptic curves exist. As was stated above, in the case of using an isomorphism, by a technical literature “On the calculation method of the elliptic curve encryption arithmetic (written by Tetsuya Izu, SCIS' 99, pp. 275–280), the probability that Weierstrass-type elliptic curves can be converted into the Montgomery-type elliptic curves is about 19/48, and therefore there is a problem that it is not always possible to convert into the Montgomery-type elliptic curves.
As was stated above, the conventional elliptic curve converting device can convert the inputted arbitrary elliptic curve, with the safety maintained, into the elliptic curve y2=x3−3x+b (the Weierstrass-type elliptic curve), there is a problem that the conversion is not always possible. Additionally, there is a problem that the conversion from Weierstrass-type elliptic curve into the Montgomery type elliptic curve is not always possible.